/* This is another implementationof my favorite triple:
   Triple[T]=(buff[T],Deque[Deque[T]],buff[T]) The buffers are
   tuple-like.

   Concat and confluence are supported.

   This is a very relaxed implementation; I think has good asymtotic
   performance, but I'm not sure that a worst case set of concats and
   deletes couldn't leave a structure with a single element at each
   level.  Measured performance at large sizes has been very good.

   I intend to patch up the concats to make this a B or B* tree even
   in worst case.

   Performance at small sizes has been disappointing.  I'm not sure
   why...  Ok, closer inspection  shows it to be use a touch slower than 
   fastest Nodal;  I think because this is accessed through the Deque
   interface.

   The name comes from the alpha method, which divides a Deque into
   its first buffer and a valid Deque.

   Henry Ware  May 2009
*/

package org.thewares.collection;

//import org.thewares.collection.Deque;
//import org.thewares.collection.ReverseDeque;

object AlphaDeque {
      def yikes=throw new Error("yikes");
      
      val empty:Deque[Nothing]=Deck0;

      // the rest of the object is private 

      private abstract class Deck[+A] extends Deque[A] {
	    override def stringPrefix = "Deque"

	    def apply(n: Int): A;
	    
	    def elements: Iterator[A];
	    def reverseElements: Iterator[A];

//	    def reverse:Deck[A];
//	    def reverseDeque=ReverseDeque(this); //hmm

	    def isEmpty: Boolean;
	    def length:Int;

	    def +[B >: A](elem: B):Deck[B];
	    def peek:A;
	    def pop:Deck[A];
	    
	    def ::[B >: A](elem: B):Deck[B];
	    def head: A;
	    def tail: Deck[A];

	    def alpha:(SmallDeck[A],Deck[A]);
	    def omega:(Deck[A],SmallDeck[A]);
	    
	    def updateFirst[B>:A](elem:B):Deck[B];
	    def updateLast[B>:A](elem:B):Deck[B];

	    override def equals(o: Any): Boolean={
		  o match {
			case d:Deck[_] => {
			      length==d.length && elements.zip(d.elements).forall{case (a,b) => a==b};
			}
			case _ => false;
		  }
	    }
	    override def hashCode(): Int={
		  (0 /: elements){case (i,a) => i ^ a.hashCode}
	    }

	    def dequeue: (A, Deck[A])=(head,tail);
	    def unshift[B >: A](elem: B):Deck[B]= elem :: this;
	    def shift: Deck[A]=tail;    
	    def enqueue[B >: A](elem: B):Deck[B]= this + elem;
	    def push[B >: A](elem: B) = this + elem;
	    def peekPop: (A, Deck[A])=(peek,pop);

	    override def foldRight[B](z: B)(op: (A, B) => B): B = {
		  var acc:B = z
		  val i=reverseElements;
	          while (i.hasNext) acc = op(i.next,acc);
	          acc
            }
	    override def :\[B](z: B)(op: (A, B) => B): B = {
		  var acc:B = z
		  val i=reverseElements;
	          while (i.hasNext) acc = op(i.next,acc);
	          acc
            }



	    def nodes:Int;
	    def depth:Int;
	    def state:String;

	    def ++[B >: A](s:Seq[B]): Deck[B] = {
		  (s) match {
			case that:Deck[B] => this ::: that;
			case s => { 
			      throw new Error("yikes");
			      val thisB:Deck[B]=this;
			      (thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    }
	    def :::[B >: A](that:Deque[B]): Deck[B];
      }

      private sealed abstract class SmallDeck[+A] extends Deck[A]{
	    def updateLast[B>:A](elem:B):SmallDeck[B];
	    def updateFirst[B>:A](elem:B):SmallDeck[B];
	    def alpha=(this,Deck0);
	    def omega=(Deck0,this);
      }
      private sealed abstract class VerySmall[+A] extends SmallDeck[A]{
		  def ::[B>:A](elem:B):SmallDeck[B];
		  def +[B>:A](elem:B):SmallDeck[B];
      }
      
      final private val SIZE=8;

      private case object Deck0 extends Deck[Nothing] {
	    def apply(n:Int):Nothing=error("element "+n+" is not in Deck0"); 
	    def elements=Iterator.empty;
	    def reverseElements=Iterator.empty;
	    override def isEmpty=true;
	    def length=0;
	    
	    def +[B](elem: B):Deck1[B]=new Deck1(elem)
	    def peek:Nothing=error("Deck0 has no elements"); 
	    def pop:Deck[Nothing]=error("Deck0 has no elements"); 
	    
	    def ::[B](elem: B):Deck1[B]=new Deck1(elem);
	    def head: Nothing=error("Deck0 has no elements"); 
	    def tail: Deck[Nothing]=error("Deck0 has no elements"); 

	    def updateFirst[B](elem:B):Nothing=error("Deck0 has no elements"); 
	    def updateLast[B](elem:B):Nothing=error("Deck0 has no elements");

	    def alpha=error("Deck0 has no elements"); 
	    def omega=error("Deck0 has no elements"); 

	    def :::[B](that:Deque[B]): Deck[B] = {
		  that match{
			case other:Deck[B] =>{
			      other
			}
			case _ => { // not optimized
			      throw new Error("yikes");
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

	    override val hashCode=0;
	    override def equals(other:Any)= other match{
		  case ed:Deck[_] => ed.length==0;
		  case _ => false;
	    }

	    def nodes=0;
	    def depth=0;
	    def state="0";
      }

      
      private[AlphaDeque] final case class Deck1[+A](_1:A) extends VerySmall[A]{
	    def apply(n:Int):A= if (n==0) {_1} else error("element "+n+" is not in Deck1");  
	    def length=1;
	    def elements=Iterator.single(_1);
	    def reverseElements=Iterator.single(_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B):Deck2[B]={
		  Deck2(_1,elem);
	    }
	    def peek:A= _1;
	    def pop:Deck[A]={
		  Deck0
	    }	    
	    def ::[B >: A](elem: B):Deck2[B]={
		  Deck2(elem,_1);
	    }
	    def head: A=_1;
	    def tail: Deck[A]= Deck0;

	    def updateFirst[B>:A](elem:B)=Deck1(elem);	     
	    def updateLast[B>:A](elem:B)=Deck1(elem);	     

	    def nodes=1;
	    def depth=1;
	    def state="1";

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match {
			case other:Deck[B] =>
			      other + _1;
			case _ => {
			      yikes
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}

		  }
	    }



      }
      private[AlphaDeque] final case class Deck8[+A](_1:A, _2:A, _3:A, _4:A, _5:A, _6:A, _7:A, _8:A) extends SmallDeck[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case 3 => _4; case 4 => _5; case 5 => _6; case 6 => _7; case 7 => _8; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=8;
	    def elements=Iterator.fromValues(_1,_2,_3,_4,_5,_6,_7,_8);
	    def reverseElements=Iterator.fromValues(_8,_7,_6,_5,_4,_3,_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new DoubleDeck(this,new Deck1(elem));

	    def peek:A= _8;
	    def pop= new Deck7(_1,_2,_3,_4,_5,_6,_7);
	    def updateLast[B>:A](elem:B)=Deck8(_1,_2,_3,_4,_5,_6,_7,elem);

	    def ::[B >: A](elem: B)= new DoubleDeck(new Deck1(elem),this);
	    def head: A= _1;
	    def tail:Deck7[A] = new Deck7(_2,_3,_4,_5,_6,_7,_8);
	    def updateFirst[B>:A](elem:B)=Deck8(elem,_2,_3,_4,_5,_6,_7,_8);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="N";

	    override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: _4 :: _5 :: _6 :: _7 :: _8 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3+_4+_5+_6+_7+_8 
			      }
	                      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      } //N
		 


      private[AlphaDeque] final case class Deck2[+A](_1:A, _2:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=2;
	    def elements=Iterator.fromValues(_1,_2);
	    def reverseElements=Iterator.fromValues(_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck3(_1,_2,elem);

	    def peek:A= _2;
	    def pop= new Deck1(_1);
	    def updateLast[B>:A](elem:B)=Deck2(_1,elem);

	    def ::[B >: A](elem: B)= new Deck3(elem,_1,_2);
	    def head: A = _1;
	    def tail:Deck1[A] = new Deck1(_2);
	    def updateFirst[B>:A](elem:B)=Deck2(elem,_2);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n


      private[AlphaDeque] final case class Deck3[+A](_1:A, _2:A, _3:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=3;
	    def elements=Iterator.fromValues(_1,_2,_3);
	    def reverseElements=Iterator.fromValues(_3,_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck4(_1,_2,_3,elem);

	    def peek:A= _3;
	    def pop= new Deck2(_1,_2);
	    def updateLast[B>:A](elem:B)=Deck3(_1,_2,elem);

	    def ::[B >: A](elem: B)= new Deck4(elem,_1,_2,_3);
	    def head: A = _1;
	    def tail:Deck2[A] = new Deck2(_2,_3);
	    def updateFirst[B>:A](elem:B)=Deck3(elem,_2,_3);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n


      private[AlphaDeque] final case class Deck4[+A](_1:A, _2:A, _3:A, _4:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case 3 => _4; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=4;
	    def elements=Iterator.fromValues(_1,_2,_3,_4);
	    def reverseElements=Iterator.fromValues(_4,_3,_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck5(_1,_2,_3,_4,elem);

	    def peek:A= _4;
	    def pop= new Deck3(_1,_2,_3);
	    def updateLast[B>:A](elem:B)=Deck4(_1,_2,_3,elem);

	    def ::[B >: A](elem: B)= new Deck5(elem,_1,_2,_3,_4);
	    def head: A = _1;
	    def tail:Deck3[A] = new Deck3(_2,_3,_4);
	    def updateFirst[B>:A](elem:B)=Deck4(elem,_2,_3,_4);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: _4 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3+_4 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n


      private[AlphaDeque] final case class Deck5[+A](_1:A, _2:A, _3:A, _4:A, _5:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case 3 => _4; case 4 => _5; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=5;
	    def elements=Iterator.fromValues(_1,_2,_3,_4,_5);
	    def reverseElements=Iterator.fromValues(_5,_4,_3,_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck6(_1,_2,_3,_4,_5,elem);

	    def peek:A= _5;
	    def pop= new Deck4(_1,_2,_3,_4);
	    def updateLast[B>:A](elem:B)=Deck5(_1,_2,_3,_4,elem);

	    def ::[B >: A](elem: B)= new Deck6(elem,_1,_2,_3,_4,_5);
	    def head: A = _1;
	    def tail:Deck4[A] = new Deck4(_2,_3,_4,_5);
	    def updateFirst[B>:A](elem:B)=Deck5(elem,_2,_3,_4,_5);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: _4 :: _5 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3+_4+_5 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n


      private[AlphaDeque] final case class Deck6[+A](_1:A, _2:A, _3:A, _4:A, _5:A, _6:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case 3 => _4; case 4 => _5; case 5 => _6; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=6;
	    def elements=Iterator.fromValues(_1,_2,_3,_4,_5,_6);
	    def reverseElements=Iterator.fromValues(_6,_5,_4,_3,_2,_1)
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck7(_1,_2,_3,_4,_5,_6,elem);

	    def peek:A= _6;
	    def pop= new Deck5(_1,_2,_3,_4,_5);
	    def updateLast[B>:A](elem:B)=Deck6(_1,_2,_3,_4,_5,elem);

	    def ::[B >: A](elem: B)= new Deck7(elem,_1,_2,_3,_4,_5,_6);
	    def head: A = _1;
	    def tail:Deck5[A] = new Deck5(_2,_3,_4,_5,_6);
	    def updateFirst[B>:A](elem:B)=Deck6(elem,_2,_3,_4,_5,_6);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: _4 :: _5 :: _6 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3+_4+_5+_6 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n


      private[AlphaDeque] final case class Deck7[+A](_1:A, _2:A, _3:A, _4:A, _5:A, _6:A, _7:A) extends VerySmall[A] {
	    def apply(n:Int):A= n match { case 0 => _1; case 1 => _2; case 2 => _3; case 3 => _4; case 4 => _5; case 5 => _6; case 6 => _7; case _ => throw new Error("index "+n+" is out of bounds");}
		  
	    def length=7;
	    def elements=Iterator.fromValues(_1,_2,_3,_4,_5,_6,_7);
	    def reverseElements=Iterator.fromValues(_7,_6,_5,_4,_3,_2,_1);
	    override def isEmpty=false;
	    
	    def +[B >: A](elem: B)= new Deck8(_1,_2,_3,_4,_5,_6,_7,elem);

	    def peek:A= _7;
	    def pop= new Deck6(_1,_2,_3,_4,_5,_6);
	    def updateLast[B>:A](elem:B)=Deck7(_1,_2,_3,_4,_5,_6,elem);

	    def ::[B >: A](elem: B)= new Deck8(elem,_1,_2,_3,_4,_5,_6,_7);
	    def head: A = _1;
	    def tail:Deck6[A] = new Deck6(_2,_3,_4,_5,_6,_7);
	    def updateFirst[B>:A](elem:B)=Deck7(elem,_2,_3,_4,_5,_6,_7);
	    	    
	    def nodes=1;
	    def depth=1;
	    def state="n";

            override def ++[B >: A](that:Seq[B]): Deck[B] = {
		  that match {
			case Deck0 => this;
			case other:Deck[B] => {
			      _1 :: _2 :: _3 :: _4 :: _5 :: _6 :: _7 :: other 
			} 
			case _ => yikes;
		  }
	    }

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  if (that.size==0){
			this;
		  } else {
			that match {
	                      case other:Deck[B] => {
			          other + _1+_2+_3+_4+_5+_6+_7 
			      }
			      case _ => {
			          yikes;
			          //val thisB:Deck[B]=this;
			          //(thisB /: that){(d,e) => d.push(e)}
			      }
			}
		  }
	    }
      
       } //n

      private[AlphaDeque] final case class DoubleDeck[+A](front:SmallDeck[A],back:SmallDeck[A]) extends Deck[A] {
	    
	    def apply(n: Int): A={
		  if (n<front.length){
			front.apply(n);
		  } else {
			back.apply(n-front.length);
		  }
	    }
	    
	    def elements: Iterator[A]= front.elements ++ back.elements;
	    def reverseElements: Iterator[A]= back.reverseElements ++ front.reverseElements;
	    override def isEmpty: Boolean= false;
	    def length:Int=front.length + back.length;

	    def +[B >: A](elem: B):Deck[B]={
		  back match{
			case vs:VerySmall[A]=> new DoubleDeck(front,vs + elem); 
			case d8: Deck8[A] =>
			      new TripleDeck(length+1,front,new Deck1(d8),new Deck1(elem)); 
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={ 
		  back.pop match {
			case Deck0 => front;
			case sd:SmallDeck[A] => new DoubleDeck(front,sd);
		  }
	    }
	    def updateLast[B>:A](elem:B)=DoubleDeck(front,back.updateLast(elem));

	    def ::[B >: A](elem: B):Deck[B]={
		  front match {
			case vs: VerySmall[A] => new DoubleDeck(elem :: vs,back);
			case d8: Deck8[A] =>
			      new TripleDeck(length+1,new Deck1(elem),new Deck1(d8),back); //k
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  val posttail=front.tail;
		  posttail match {
			case Deck0 => back;
			case sd:SmallDeck[A] => new DoubleDeck(sd,back);
		  }
	    }
	    def updateFirst[B>:A](elem:B)=DoubleDeck(front.updateFirst(elem),back);
	     
	    // fixme: leave 8 behind
	    def alpha=(front,back);
	    def omega=(front,back);

	    def nodes=1+front.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  1+ (if (fd>bd) fd else bd)
	    }
	    def state="["+front.state+","+back.state+"]";
	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case Deck0 => this;
			case d:SmallDeck[B] => d ++ this;
			case DoubleDeck(a,b) =>{
			      // fixme: make sure there is no hole buildup
			      val len=that.length+this.length;
			      if (b.length+front.length <= SIZE){
				    TripleDeck(len,a, Deck1(b ++ front), back);
			      } else {
				    TripleDeck(len,a,Deck2(b,front),back);
			      }
			}
			case TripleDeck(n,a,b,c) => {
			      val (psi,ome)=omega;
			      TripleDeck(n,a,b+c+psi,ome);
			}
			case _ => { // not optimized
			      yikes
			      //val thisB:Deck[B]=this;
			      //(thisB /: that){(d,e) => d.push(e)}
			}
		  }
	    } // end :::
      }

      sealed private trait IState;
      final private case object FrontState extends IState{};
      final private case object UpState extends IState{};
      final private case object BackState extends IState{}
      final private case object NoState extends IState{};


      // non of these subdeques are empty
      private[AlphaDeque] final case class TripleDeck[+A](N:Int,front:SmallDeck[A],up:Deck[Deck[A]],back:SmallDeck[A]) extends Deck[A] {
	    
	    // slow.
	    def apply(n: Int): A= elements.drop(n).next();
	    
	    // up=DDT, UP.elements=IDT, UP.map(elements)=D(IT) ok at
	    // 260 per def elements: Iterator[A]= front.elements ++
	    // up.elements.flatMap(_.elements) ++ back.elements;
	    def elements=new Iterator[A]{
		  var state:IState=FrontState;
		  var i=front.elements;
		  var j:Iterator[Deque[A]]=Iterator.empty;
		  def hasNext={
			if (i.hasNext){
			      true;
			} else {
			      state match{
				    case FrontState => { j=up.elements; i=j.next.elements; state=UpState; true }
				    case UpState => {if (j.hasNext) {i=j.next.elements; true} else {i=back.elements; j=null; state=BackState; true}}
				    case BackState => {state=NoState; i=Iterator.empty; false; }
				    case NoState => false;
			      }
			}
		  }
		  def next={hasNext; i.next;}
	    }

	    def reverseElements=new Iterator[A]{
		  var state:IState=BackState;
		  var i=back.reverseElements;
		  var j:Iterator[Deque[A]]=Iterator.empty;
		  def hasNext={
			if (i.hasNext){
			      true;
			} else {
			      state match{
				    case BackState => { j=up.reverseElements; i=j.next.reverseElements; state=UpState; true }
				    case UpState => {if (j.hasNext) {i=j.next.reverseElements; true} 
						     else {i=front.reverseElements; j=null; state=FrontState; true}}
				    case FrontState => {state=NoState; i=Iterator.empty; false; }
				    case NoState => false;
			      }
			}
		  }
		  def next={hasNext; i.next;}
	    }

	    override def isEmpty: Boolean= false;
	    def length:Int=N;
	    
	    def +[B >: A](elem: B):Deck[B]={
		  back match {
			case d8:Deck8[B] => new TripleDeck(N+1,front,up + back,new Deck1(elem));
		  	case vs:VerySmall[B] => new TripleDeck(N+1,front,up,vs + elem);
		  }
	    }
	    def peek:A=back.peek;
	    def pop:Deck[A]={
		  back.pop match {
			case sd:SmallDeck[A] =>  TripleDeck(N-1,front,up,sd);
			case Deck0 => {
			      val (me,deck1)=omega;
			      me;
			}
		  }
	    }
	    def updateLast[B>:A](elem:B)=TripleDeck(N,front,up,back.updateLast(elem));
	    
	    def ::[B >: A](elem: B):Deck[B]={
		  front match {
			case d8:Deck8[A] => new TripleDeck(N+1,Deck1(elem),d8 :: up,back);
			case vs:VerySmall[A] => new TripleDeck(N+1,elem :: vs,up,back);
		  }
	    }
	    def head: A=front.head;
	    def tail: Deck[A]={
		  front.tail match {
			case Deck0 =>{val (empty,me)=alpha;me};
			case sd:SmallDeck[A] => TripleDeck(N-1,sd,up,back);
		  }
	    }
	    def updateFirst[B>:A](elem:B)=TripleDeck(N,front.updateFirst(elem),up,back);

	    def alpha={ 
		  up.head match {
			case beta:SmallDeck[A] => {
			      up.tail match {
				    case Deck0 => (front,DoubleDeck(beta,back));
				    case upsilon:Deck[A] => (front,TripleDeck(N-front.length,beta,upsilon,back));
			      }
			}
			case d:Deck[A] => {
			      val (beta,dd)=d.alpha;
			      dd match {
				    case Deck0 => (front,TripleDeck(N-front.length,beta,up.tail,back));
				    case _ => (front,TripleDeck(N-front.length,beta,up.updateFirst(dd),back));
			      }
			}
		  }
	    }
	    def omega={ 
		  // the tricky bit is the next to last
		  up.peek match {
			case psi:SmallDeck[A] => {
			      up.pop match {
				    case Deck0 => (DoubleDeck(front,psi),back);
				    case upsilon:Deck[A] => (TripleDeck(N-back.length,front,upsilon,psi),back);
			      }
			}
			case d:Deck[A] => {
			      val (dd,psi)=d.omega;
			      dd match {
				    case Deck0 => (TripleDeck(N-back.length,front,up.pop,psi),back);
				    case _ => (TripleDeck(N-back.length,front,up.updateLast(dd),psi),back);
			      }
			}
		  }
	    }
	    
	    def nodes=1+front.nodes+up.nodes+back.nodes;
	    def depth={
		  val fd=front.depth;
		  val bd=back.depth;
		  val mfb=if (fd>bd) fd else bd;
		  val ud=up.depth;
		  1+ (if (ud>mfb) ud else mfb);
	    }
	    def state="("+front.state+","+up.state+","+back.state+")";

	    def :::[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case Deck0 => this;
			case d:SmallDeck[B] => d ++ this;
			case d:DoubleDeck[B] => {
			      val (alp,bet)=d.alpha;
			      TripleDeck(N+that.length, alp, bet :: front :: up, back);
			}
			case d:TripleDeck[B] =>{
			      val (alp,bet)=d.alpha;
			      TripleDeck(d.length+N,alp,bet :: front :: up ,back);
			}
			case that:Deque[B] => { // not optimized
			      yikes;
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

	    def ++[B >: A](that:Deque[B]): Deck[B] = {
		  that match{
			case Deck0 => this;
			case d:SmallDeck[B] =>  this ::: d;
			case d:DoubleDeck[B] => {
			      val (psi,ome)=d.omega;
			      TripleDeck(N+that.length, front, up + back + psi, back);
			}
			case d:TripleDeck[B] =>{
			      val (psi,ome)=d.omega;
			      TripleDeck(d.length+N,front,up+back+psi,ome);
			}
			case that:Deque[B] => { // not optimized
			      yikes;
			      //val thisB:Deck[B]=this;
			      //(thisB /: s){(d,e) => d.push(e)}
			}
		  }
	    } // end :::

      }// end TripleDeck

}
